BZOJ 2006 超级钢琴

Description

小Z是一个小有名气的钢琴家,最近C博士送给了小Z一架超级钢琴,小Z希望能够用这架钢琴创作出世界上最美妙的音乐。 这架超级钢琴可以弹奏出n个音符,编号为1至n。第i个音符的美妙度为Ai,其中Ai可正可负。 一个“超级和弦”由若干个编号连续的音符组成,包含的音符个数不少于L且不多于R。我们定义超级和弦的美妙度为其包含的所有音符的美妙度之和。两个超级和弦被认为是相同的,当且仅当这两个超级和弦所包含的音符集合是相同的。 小Z决定创作一首由k个超级和弦组成的乐曲,为了使得乐曲更加动听,小Z要求该乐曲由k个不同的超级和弦组成。我们定义一首乐曲的美妙度为其所包含的所有超级和弦的美妙度之和。小Z想知道他能够创作出来的乐曲美妙度最大值是多少。

Input

第一行包含四个正整数n, k, L, R。其中n为音符的个数,k为乐曲所包含的超级和弦个数,L和R分别是超级和弦所包含音符个数的下限和上限。 接下来n行,每行包含一个整数Ai,表示按编号从小到大每个音符的美妙度。

Output

只有一个整数,表示乐曲美妙度的最大值。

Sample Input

4 3 2 3
3
2
-6
8

Sample Output11

11

Hint

【样例说明】
共有5种不同的超级和弦:
音符1 ~ 2,美妙度为3 + 2 = 5
音符2 ~ 3,美妙度为2 + (-6) = -4
音符3 ~ 4,美妙度为(-6) + 8 = 2
音符1 ~ 3,美妙度为3 + 2 + (-6) = -1
音符2 ~ 4,美妙度为2 + (-6) + 8 = 4
最优方案为:乐曲由和弦1,和弦3,和弦5组成,美妙度为5 + 2 + 4 = 11。

Solution

搞个主席树+堆存一下,log从堆里取一个,log再从主席树里找一个

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include<bits/stdc++.h>

#define maxn 500000+5
#define maxt 10000000+5
#define set(a,b) memset(a,(b),sizeof(a))

using namespace std;

typedef long long ll;

struct group{
ll val,sum;
int pos,rank;
friend bool operator > (const group &a,const group &b){return a.val<b.val;}
};

struct disct{
ll w;int id;
}disc[maxn];

struct segtree{
int s[2],sum;
}tr[maxt];

ll ans,sum[maxn];
priority_queue<group,vector<group>,greater<group> > q;
int L[maxn],R[maxn],pos[maxn];
int root[maxn],size;
int n,l,r,k;

bool comp(disct a,disct b)
{

return a.w<b.w;
}

void update(int x)
{

int l=tr[x].s[0],r=tr[x].s[1];
tr[x].sum=tr[l].sum+tr[r].sum;
}

void insert(int &x,int y,int l,int r,int w)
{

if( w<l || r<w ) return ;
x=++size;
tr[x]=tr[y];
if( l==r ){
tr[x].sum++;
return ;
}
insert(tr[x].s[0],tr[y].s[0],l,(l+r)/2,w);
insert(tr[x].s[1],tr[y].s[1],(l+r)/2+1,r,w);
update(x);
}

ll query(int x,int y,int l,int r,int t)
{

if( l==r ) return disc[l].w;
int ls=tr[tr[x].s[0]].sum-tr[tr[y].s[0]].sum;
if( t<=ls ) return query(tr[x].s[0],tr[y].s[0],l,(l+r)/2,t);
else return query(tr[x].s[1],tr[y].s[1],(l+r)/2+1,r,t-ls);
}

int main()
{

#ifndef ONLINE_JUDGE
freopen("2006.in","r",stdin);
freopen("2006.out","w",stdout);
#endif
scanf("%d%d%d%d",&n,&k,&l,&r);
l-=1,r-=1;
for(int i=1;i<=n;i++){
scanf("%lld",&sum[i]);
sum[i]+=sum[i-1];
disc[i].w=sum[i],disc[i].id=i;
}
sort(disc+1,disc+n+1,comp);
for(int i=1;i<=n;i++) pos[disc[i].id]=i;
for(int i=1;i<=n;i++) insert(root[i],root[i-1],1,n,pos[i]);
for(int i=1;i<=n-l;i++){
ll w;
L[i]=i+l,R[i]=min(i+r,n);
w=query(root[R[i]],root[L[i]-1],1,n,R[i]-L[i]+1);
q.push((group){w-sum[i-1],sum[i-1],i,R[i]-L[i]+1});
}
for(int i=1;i<=k;i++){
group sd=q.top();q.pop();
ans+=sd.val;
if( sd.rank>1 ){
ll w=query(root[R[sd.pos]],root[L[sd.pos]-1],1,n,sd.rank-1);
q.push((group){w-sd.sum,sd.sum,sd.pos,sd.rank-1});
}
}
printf("%lld",ans);
return 0;
}